1. Field of the Invention
This invention relates to digital maps of the type for displaying road or pathway information, and more particularly toward a method for updating information contained in a digital map using reliable probe data as well as a method for matching a mobile navigation device to a digital map using only reliable GPS data.
2. Related Art
Personal navigation devices like that shown for example in FIG. 1 utilize digital maps combined with accurate positioning data from GPS or other data streams. These devices have been developed for commuters seeking navigation assistance, for businesses trying to minimize transportation costs, and many other applications. The effectiveness of such navigation systems in inherently dependent upon the accuracy and completeness of the information provided to it in the form of digital maps and associated attribute data. Likewise, the effectiveness of such navigation systems is also dependent upon accurately and quickly matching the actual, real-world location of the navigation device to a corresponding portion of the digital map. Typically, the navigation system includes a small display screen or graphic user interface that portrays a network of streets as a series of line segments, including a center line running approximately along the center of each street or path, as exemplified in FIG. 1. The traveler can then be generally located on the digital map close to or with regard to that center line. Such GPS-enabled personal navigation devices, such as those manufactured by TomTom N.V. (www.tomtom.com) may be also configured with probes to generate probe data points. Of course, other suitable devices may be used to generate probe data points including handheld devices, mobile phones, PDAs, and the like.
Digital maps are expensive to produce and update, since exhibiting and processing road information is very costly. Surveying methods or digitizing satellite images have been employed in the past for creating digital maps, but are prone to the introduction of inaccuracies or systematic errors due to faulty or inaccurate input sources or flawed inference procedures. Once a digital map has been created, it is costly to keep map information up to date, since road geometry changes over time.
FIG. 2 illustrates a fractional section of a digital map, in this case a by-directional roadway supporting two-way traffic. A main trunk of the roadway is indicated at 10 and a branch road extending generally perpendicularly from the main trunk 10 is indicated at 12.
It is known, for example, to take probe data inputs (i.e., time-stamped position recordings at regular intervals) from low-cost positioning systems and handheld devices and mobile phones with integrated GPS functionality for the purpose of incrementally learning a map using certain clustering technologies. The input to be processed consists of recorded GPS traces in the form of a standard ASCII stream, which is supported by almost all existing GPS devices. The output is a road map in the form of a directed graph with nodes and edges associated with travel time information. Travelers appropriately fitted with navigation devices may thus produce a trace map in the form of probe data, with nodes created at regular distances. The nodes and edges are stored in a digital map table or database. Through this technique, road geometry can be inferred and the collected probe data points refined by filtering and partitioning algorithms. For a more complete discussion of this technique, reference is made to “Incremental Map Generation with GPS Traces,” Brüntrup, R., Edelkamp, S., Jabbar, S., Scholz, B., Proc. 8th Int. IEEE Conf. on Intelligent Transportation Systems, Vienna, Austria, 2005, pages 413-418.
One issue associated with such methods for generating and updating digital maps using probe data relates to certain accuracy issues associated with GPS measurements. As is well known, GPS is based on concepts of satellite ranging, wherein the distances between the GPS receiver and four or more satellites are calculated, as represented illustratively in FIG. 3. Assuming the positions of the satellites 22 are known, the location of the receiver 14 can be calculated by determining the distance from each satellite 22 to the receiver 14. Distance measurements are determined by measuring the amount of time it takes the GPS radio signal 20 to travel from the satellite 22 to the receiver 14. Radio waves travel at the speed of light. Therefore, if the amount of time it takes for the GPS signal to travel from the satellite 22 to the receiver 14 is known, the distance (distance=speed×time) can be determined. Thus, if the exact time when the signal 20 was transmitted and the exact time when it was received or known, the signal's travel time can be easily calculated.
GPS systems are designed to be as nearly accurate as possible, however various factors are known to introduce errors. Added together, these errors cause deviations in the calculated position of the GPS receiver. Several sources for errors are known, some of which include: atmospheric conditions, ephemeris errors, clock drift, measurement noise, selective availability and multi-path. Multi-path error is a serious concern for GPS users. Multi-path is caused by a GPS signal 20 bouncing off of a reflective surface prior to reaching the GPS receiver antenna 14. It is difficult to completely correct multi-path error, even in high precision GPS units. FIG. 4 is a schematic view describing the multi-path phenomenon. A GPS antenna 14 is stationed between first 16 and second 18 obstacles, which may, for example, represent tall buildings in a city center environment. A GPS signal 20 from one GPS satellite 22 is received without corruption, however a signal 24 from another satellite 26 encounters the first obstacle 16 so that its signal 24 does not proceed directly to the GPS antenna 14. A corrupt signal 24′ from the satellite 26, however, is reflected off the second obstacle 18 and received by the GPS antenna 14. Reflection of the corrupted signal 24′ results in a situation where it takes longer for the signal 24′ to reach the GPS antenna 14 than it should have. This time lag results in a perceived position shift of the GPS antenna 14 from its actual position in real life. FIG. 5 shows a sample trace path from probe data created by a personal navigation device utilizing the antenna 14. The real, actual position of the moving probe is represented by the straight line 28 and the calculated position of the GPS antenna 14 is represented by the path 30. As shown, the calculated position of the GPS antenna 14 demonstrates corruption due to the effects of multi-path.
Various techniques can be employed to counteract the effects of GPS error, including techniques related to the Dilution of Precision, or DOP. DOP is an indicator of the quality of the geometry of the satellite constellation, such as that depicted generally in FIG. 3. The computed position of the GPS antenna 14 can vary depending on which satellites are used for the measurements. Different satellite geometries can magnify or lessen the errors in the error budget. A greater angle between the satellites will lower the DOP and provide a better measurement. A higher DOP indicates poor satellite geometry, and an inferior measurement configuration. Some GPS receivers are able to analyze the positions of the available satellites and choose only those satellites with the best geometry in order to make the DOP as low as possible. With regard to multi-path, errors introduced by local reflections cannot easily be detected using DOP satellite selection techniques.
Accordingly, there is a need for an improved method to receive probe data, such as that from GPS-enabled navigation devices, for the purpose of improving existing map networks and generating new network elements in the practice of digital map making. Furthermore, there is a need for improved matching of a GPS receiver position relative to a digital map in which the negative effects of multi-path are, at least partially, counteracted.